package cz.cvut.kadledav.paa.knapsack.tasks;

import java.util.Set;

/**
 * User: David Kadlecek
 * Date: 31.10.13
 */
public class TestMain {
    static int[] values = new int[] {5, 9, 20, 12, 18};
    static int[] weights = new int[] {2, 6, 5, 3, 4};
    static int[][] memory = new int[values.length][65];

    private static int knapsack(int i, int W) {
        if (i < 0) {
            return 0;
        }
        int mem = memory[i][W];
        if(mem>0){
            return mem;
        }
        int nextI = i - 1;
        if (weights[i] > W) {
            return knapsack(nextI, W);
        } else {
            int c1 = knapsack(nextI, W);

            int smallerW = W - weights[i];
            int c2 = knapsack(nextI, smallerW) + values[i];

            if(c1>c2){
                mem = memory[nextI][ W ];
//                save(nextI,W,c1);
                return c1;
            } else {
//                save(nextI,smallerW,c2);
                return c2;
            }
        }
    }

    private static void save(int i, int w, int c) {
        if(i<0){
            return;
        }
        int mem = memory[i][ w ];
        if(c > mem){
            memory[i][ w ] = c;
        }
    }

    public static void main(String[] args) {
//        System.out.println(knapsack(values.length - 1, 10));
        DynamicProgramingByCostTask dynamicProgramingTask = new DynamicProgramingByCostTask();
//        dynamicProgramingTask.prices = new int[]{5,9,20,12,18};
//        dynamicProgramingTask.weights = new int[]{2,6,5,3,4};
        dynamicProgramingTask.prices = new int[]{20,5,9,12,18};
        dynamicProgramingTask.weights = new int[]{5,2,6,3,4};
        dynamicProgramingTask.maxAllowedWeight = 10;
        dynamicProgramingTask.compute();
        Set<Integer> computedItemsIds = dynamicProgramingTask.getComputedItemsIds();
        System.out.print(dynamicProgramingTask.getMaximumPrice());
    }
}
